package BFS;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-11
 * Time:15:47
 * Text：127. 单词接龙
 */
public class Texts4 {
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public int bfs(int[][] array,int bx,int by,int zx,int zy)
    {
        if(bx==zx && by==zy) return 0;
        Queue<int[]> q=new LinkedList<>();
        boolean[][] vis=new boolean[array.length][array[0].length];
        int ret=0;
        q.add(new int[]{bx,by});
        vis[bx][by]=true;
        while(!q.isEmpty())
        {
            ret++;
            int size=q.size();
            while(size-->0)
            {
                int[] xy=q.poll();
                int x=xy[0],y=xy[1];
                for(int i=0;i<4;i++)
                {
                    int x1=x+dx[i],y1=y+dy[i];
                    if(x1>=0 && x1<array.length && y1>=0 && y1<array[0].length && array[x1][y1]!=0 && !vis[x1][y1])
                    {
                        if(x1 == zx && y1 == zy)   //砍中树了
                        {
                            return ret;
                        }
                        else
                        {
                            vis[x1][y1]=true;
                            q.add(new int[]{x1,y1});
                        }
                    }
                }
            }
        }
        return -1;
    }
    public int cutOffTree(List<List<Integer>> forest) {
        int[][] array=new int[forest.size()][forest.get(0).size()];
        List<int[]> t1=new LinkedList<>();
        int num=0;
        for(List<Integer> t2: forest)
        {
            int numy=0;
            for(int a:t2)
            {
                if(a!=0 && a!=1)
                    t1.add(new int[]{num,numy});  //将需要砍的树下标加进去
                array[num][numy++]=a;
            }
            num++;
        }
        Collections.sort(t1,(a,b) -> {
            return forest.get(a[0]).get(a[1])-forest.get(b[0]).get(b[1]);
        });

        int ret=0;
        int bx=0,by=0;
        for(int[] tree:t1)
        {
            int x=tree[0],y=tree[1];
            int step=bfs(array,bx,by,x,y);
            ret+=step;
            if(step==-1) return -1;
            bx=x;
            by=y;
        }
        return ret;
    }
}
